package 剑指offer;

public class _68二叉树的最近公共祖先 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    TreeNode lac;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        find(root,p,q);
        return lac;
    }

    private boolean find(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return false;
        }
        int left = find(root.left,p,q) ? 1 : 0;
        int right = find(root.right,p,q) ? 1 : 0;
        int mid = (root == p || root == q) ? 1 : 0;
        if(left + right + mid == 2){
            lac = root;
            return true;
        }
        return (left + right + mid) > 0;
    }

    public static void main(String[] args) {

    }
}
